{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Swap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSwap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大交换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数，你<strong>至多</strong>可以交换一次数字中的任意两位。返回你能得到的最大值。</p>\n",
    "\n",
    "<p><strong>示例 1 :</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 2736\n",
    "<strong>输出:</strong> 7236\n",
    "<strong>解释:</strong> 交换数字2和数字7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 :</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 9973\n",
    "<strong>输出:</strong> 9973\n",
    "<strong>解释:</strong> 不需要交换。\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>给定数字的范围是&nbsp;[0, 10<sup>8</sup>]</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-swap](https://leetcode.cn/problems/maximum-swap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-swap](https://leetcode.cn/problems/maximum-swap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2736', '9973']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        \n",
    "        s = str(num)\n",
    "        for i in range(len(s)-1):\n",
    "            next_max = max(s[i+1:])\n",
    "            if next_max > s[i]:\n",
    "                loc = i + s[i+1:].rfind(next_max) + 1\n",
    "                return int(s[:i] + next_max + s[i+1:loc] + s[i] + s[loc+1:])\n",
    "        \n",
    "        return num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num_str = [ i for i in str(num)]\n",
    "        num_sort = sorted(num_str,reverse = True)\n",
    "        for i in range(len(num_str)):\n",
    "            if num_sort[i] != num_str[i]:\n",
    "                j = len(num_str) - num_str[::-1].index(num_sort[i]) - 1\n",
    "                num_str[i],num_str[j] = num_str[j],num_str[i]\n",
    "                break\n",
    "        return int(''.join(num_str))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        str_num=str(num)\n",
    "        if len(str_num)==1:\n",
    "            return num\n",
    "        list_num=list(str_num)\n",
    "        sorted_num=sorted(list_num,key=lambda x:-1*ord(x))\n",
    "        if list_num==sorted_num:\n",
    "            return num\n",
    "        i=0\n",
    "        while list_num[i]==sorted_num[i]:\n",
    "            i+=1\n",
    "        k=len(sorted_num)-1\n",
    "        while list_num[k]!=sorted_num[i]:\n",
    "            k-=1\n",
    "        list_num[k]=list_num[i]\n",
    "        list_num[i]=sorted_num[i]\n",
    "        return int(\"\".join(list_num))\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        c_list = [n for n in str(num)]\n",
    "        left, right = None, None\n",
    "        for i, n in enumerate(c_list):\n",
    "            max_c = '0'\n",
    "            max_idx = -1\n",
    "            for j in range(len(c_list) - 1, i, -1):\n",
    "                if c_list[j] > max_c:\n",
    "                    max_c = c_list[j]\n",
    "                    max_idx = j\n",
    "            if max_c > c_list[i]:\n",
    "                tmp = c_list[max_idx]\n",
    "                c_list[max_idx] = c_list[i]\n",
    "                c_list[i] = tmp\n",
    "                break\n",
    "        return int(''.join(c_list))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: 'int') -> 'int':\n",
    "        strnum=str(num)\n",
    "        for x in range(len(strnum)):\n",
    "            maxnum = max(strnum[x:])\n",
    "            if strnum[x] != maxnum:\n",
    "                y=len(strnum)-strnum[::-1].find(maxnum)-1\n",
    "                return int(strnum[:x]+strnum[y]+strnum[x+1:y]+strnum[x]+strnum[y+1:])\n",
    "        else:\n",
    "            return num\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        digits = []\n",
    "        i = 0\n",
    "        m = 0\n",
    "        while num > 0:\n",
    "            q, r = divmod(num, 10)\n",
    "            digits.insert(0, str(r))\n",
    "            num = q\n",
    "\n",
    "        digits2 = sorted(digits, reverse=True)\n",
    "        n = len(digits)\n",
    "\n",
    "        for i in range(n):\n",
    "            a, b = digits[i], digits2[i]\n",
    "            if a == b:\n",
    "                continue\n",
    "\n",
    "            digits[i] = b\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if digits[j] == b:\n",
    "                    digits[j] = a\n",
    "                    break\n",
    "\n",
    "            break\n",
    "\n",
    "        return int(\"\".join(digits))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: 'int') -> 'int':\n",
    "        nums = list(str(num))\n",
    "        rmax = ['0' for x in nums]\n",
    "        \n",
    "        nlen = len(nums)\n",
    "        maxi = '0'\n",
    "        for i in range(nlen-1, -1, -1):\n",
    "            rmax[i] = maxi\n",
    "            maxi = max(maxi, nums[i])\n",
    "        print(rmax)\n",
    "        l = -1\n",
    "        r = nlen\n",
    "        for i in range(nlen):\n",
    "            if nums[i] < rmax[i]:\n",
    "                l = i\n",
    "                break\n",
    "        if l == -1:\n",
    "            return num\n",
    "        for i in range(nlen-1,-1,-1):\n",
    "            if nums[i] == rmax[l]:\n",
    "                r = i\n",
    "                break\n",
    "        tmp = nums[l]\n",
    "        nums[l] = nums[r]\n",
    "        nums[r] = tmp\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            res *= 10\n",
    "            res += int(n)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        list=[int(i) for i in str(num)]\n",
    "        compare=sorted(list,reverse=True)\n",
    "        if compare==list:\n",
    "            return num\n",
    "        else:\n",
    "            for i in range(len(list)):\n",
    "                if list[i]!=compare[i]:\n",
    "                    j=len(list)-(list[::-1].index(compare[i]))-1\n",
    "                    list[i],list[j]=compare[i],list[i]\n",
    "                    break\n",
    "            return int(\"\".join([str(i) for i in list]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        import functools as f\n",
    "        list1 = list(str(num))\n",
    "        list0 = []\n",
    "        while True:\n",
    "            if len(list1) in (0, 1):\n",
    "                return f.reduce(lambda x, y: 10 * int(x) + int(y), list0 + list1)\n",
    "            if list1[0] == max(list1):\n",
    "                list0.append(list1.pop(0))\n",
    "            else:\n",
    "                break\n",
    "        for i in range(len(list1) - 1, 0, -1):\n",
    "            if list1[i] == max(list1):\n",
    "                list1[i], list1[0] = list1[0], list1[i]\n",
    "                return f.reduce(lambda x, y: 10 * int(x) + int(y), list0 + list1)\n",
    "            \n",
    "    \n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "    \n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        num_list = []\n",
    "        while num != 0:\n",
    "            curr_num = int(num % 10)\n",
    "            num = int(num / 10)\n",
    "            num_list.insert(0, curr_num)\n",
    "        length = len(num_list)\n",
    "        for index in range(length-1):\n",
    "            curr_num = num_list[index]\n",
    "            sub_num_list = num_list[index + 1:]\n",
    "            sub_num_list_max = max(sub_num_list)\n",
    "            if curr_num < sub_num_list_max:\n",
    "                max_index = self.helper(sub_num_list, sub_num_list_max) + index + 1\n",
    "                num_list[index] = sub_num_list_max\n",
    "                num_list[max_index] = curr_num\n",
    "                break\n",
    "        result = 0\n",
    "        for index in range(length):\n",
    "            result += num_list[index] * pow(10, length - 1 - index)\n",
    "        return result\n",
    "\n",
    "    def helper(self, nums_list, target):\n",
    "        length = len(nums_list) - 1\n",
    "        while length >= 0:\n",
    "            if nums_list[length] == target:\n",
    "                return length\n",
    "            length -= 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        string = list(str(num))\n",
    "        n = len(string)\n",
    "        s, idx_max = [], n-1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if string[i] > string[idx_max]:\n",
    "                idx_max = i\n",
    "            s.append(idx_max)\n",
    "        s.reverse()\n",
    "        for i in range(n):\n",
    "            if string[s[i]] > string[i]:\n",
    "                string[i], string[s[i]] = string[s[i]], string[i]\n",
    "                break                \n",
    "        return int(''.join(string))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        num2 = list(str(num))\n",
    "        index_max = [-1]*10\n",
    "        index_small = [-1]*10\n",
    "        for i in range(len(num2)):\n",
    "            if index_max[int(num2[i])] <i:\n",
    "                index_max[int(num2[i])]=i\n",
    "            if index_small[int(num2[i])]==-1:\n",
    "                index_small[int(num2[i])]=i\n",
    "                \n",
    "        for i in range(len(index_max)-1,-1,-1):\n",
    "            swap = index_max[i]\n",
    "            for j in range(i):\n",
    "                \n",
    "                if index_small[j]<index_max[i] and index_small[i]!=-1 and index_max[j]!=-1:\n",
    "                    if index_small[j]<swap:\n",
    "                        swap = index_small[j]\n",
    "            if swap<index_max[i]:\n",
    "                temp = num2[swap]\n",
    "                num2[swap]=num2[index_max[i]]\n",
    "                num2[index_max[i]] =temp\n",
    "                c=''.join(num2)\n",
    "                return int(c)\n",
    "        return num\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "\n",
    "        def cal(nums):\n",
    "            r = 0\n",
    "            for n in nums:\n",
    "                r = r * 10 + n\n",
    "            return r\n",
    "\n",
    "        nums = []\n",
    "        while num:\n",
    "            nums.append(num %10)\n",
    "            num //= 10\n",
    "        \n",
    "        pos = {}\n",
    "        nums = nums[::-1]\n",
    "        nums_sort = sorted(nums, reverse=True)\n",
    "        \n",
    "        for i, e in enumerate(nums):\n",
    "            if e not in pos:\n",
    "                pos[e] = []\n",
    "            pos[e].append(i)\n",
    "\n",
    "        for i, e in enumerate(nums):\n",
    "            if e != nums_sort[i]:\n",
    "                j = pos[nums_sort[i]][-1]\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                break\n",
    "\n",
    "        return cal(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        nums = list(str(num))\n",
    "        max_idx = len(nums)-1\n",
    "        l,r = 0,0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]>nums[max_idx]:\n",
    "                max_idx=i\n",
    "            elif nums[i]<nums[max_idx]:\n",
    "                l = i\n",
    "                r = max_idx\n",
    "        nums[l],nums[r]=nums[r],nums[l]\n",
    "        return ''.join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class LinkNode:\n",
    "    def __init__(self, index, val):\n",
    "        self.index = [index]\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right =None\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        head = None\n",
    "        for i, digit in enumerate(str(num)):\n",
    "            node = LinkNode(i, int(digit))\n",
    "            if not head:\n",
    "                head = node\n",
    "            else:\n",
    "                self.insert_node(head, node)\n",
    "        left, right = self.extract_swap_index(head)\n",
    "        if left != None:\n",
    "            num_str = list(str(num))\n",
    "            temp = num_str[left]\n",
    "            num_str[left] = num_str[right]\n",
    "            num_str[right] = temp\n",
    "            num = reduce(lambda x, y: x +y, num_str)\n",
    "        return int(num)\n",
    "\n",
    "    def insert_node(self, head, node):\n",
    "        if node.val <= head.val:\n",
    "            if head.val == node.val:\n",
    "                head.index.append(node.index[0])\n",
    "            if not head.left:\n",
    "                head.left = node\n",
    "                return\n",
    "            head = head.left\n",
    "            self.insert_node(head, node)\n",
    "        elif node.val > head.val:\n",
    "            if not head.right:\n",
    "                head.right = node\n",
    "                return\n",
    "            head = head.right\n",
    "            self.insert_node(head, node)\n",
    "\n",
    "    def extract_swap_index(self, head):\n",
    "        left = None\n",
    "        right = None\n",
    "        while head and head.right == None:\n",
    "            head = head.left\n",
    "        if head:\n",
    "            left = head.index[0]\n",
    "            while head.right != None:\n",
    "                head = head.right\n",
    "            right = head.index[-1]\n",
    "        return left, right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        l = list(s)\n",
    "        l = [int(item) for item in l]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        find = 0\n",
    "        temp = 0\n",
    "        if len(l) == 1:\n",
    "            return num\n",
    "\n",
    "        for i in range(len(l) - 1):\n",
    "            temp = max(l[i + 1:])\n",
    "            if l[i] < temp:\n",
    "                find = 1\n",
    "                break\n",
    "        print(l)\n",
    "        ll = l[::-1]\n",
    "        print(ll, temp, ll.index(temp))\n",
    "        j = len(l) - (ll.index(temp) + 1)\n",
    "        l = [str(item) for item in l]\n",
    "        print(i, j)\n",
    "        if find == 1:\n",
    "            temp = l[i]\n",
    "            l[i] = l[j]\n",
    "            l[j] = temp\n",
    "        return int(''.join(l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        nums=list(str(num))\n",
    "        tmp=-1\n",
    "        nums_tmp=sorted(nums,reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]!=nums_tmp[i]:\n",
    "                tmp=i\n",
    "                break\n",
    "        if tmp>=0:\n",
    "            for i in range(len(nums)-1,tmp,-1):\n",
    "                if nums[i]==nums_tmp[tmp]:\n",
    "                    nums[tmp],nums[i]=nums[i],nums[tmp]\n",
    "                    break\n",
    "        return int(''.join(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        digits = list(str(num)) # 将输入数字转换成字符数组\n",
    "        n = len(digits)\n",
    "        pos = [-1] * 10 # 记录 0~9 这十个数字出现位置的最近下标，初始化为 -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            pos[int(digits[i])] = i # 更新当前数字出现最新的下标\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(9, int(digits[i]), -1): # 从高到低枚举右侧的数字\n",
    "                if pos[j] > i: # 如果这个数字还在当前位置的右侧，则可以进行交换\n",
    "                    digits[i], digits[pos[j]] = digits[pos[j]], digits[i]\n",
    "                    return int(''.join(digits)) # 直接将字符数组拼接起来返回即可\n",
    "        \n",
    "        return num # 如果不用交换就是最大数，直接返回原始数字即可\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        num1 = []\n",
    "        p=num\n",
    "        while p:\n",
    "            num1.insert(0,p%10)\n",
    "            p = p//10\n",
    "        num2=[[i,j]for i,j in enumerate(num1)]\n",
    "        # 大的数字排前面；相同发数字，靠右的排前面\n",
    "        num2.sort(key=lambda x:(-x[1],-x[0])) \n",
    "\n",
    "        # 找出待替换的位置位置(p1)；待替换到p1的值to_replace\n",
    "        p1,p2=0,0\n",
    "        while p1 != len(num1) and num1[p1]==num2[p2][1]:\n",
    "            p1+=1\n",
    "            p2+=1\n",
    "        \n",
    "        # 已经是最大了\n",
    "        if p1 == len(num1):\n",
    "            return num\n",
    "\n",
    "        to_replace = num2[p2][1]\n",
    "        # 如果需要替换，找出最靠右的值(num2中第一个)\n",
    "        for i,j in num2:\n",
    "            if j == to_replace:\n",
    "                num2[p2][0] = i\n",
    "                break\n",
    "        num1[p1],num1[num2[p2][0]]=num1[num2[p2][0]],num1[p1]\n",
    "        return int(''.join([str(i) for i in num1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        n_list = []\n",
    "        tmp = num\n",
    "        while tmp > 0:\n",
    "            n_list.append(tmp % 10)\n",
    "            tmp = tmp // 10\n",
    "        n = len(n_list)\n",
    "        idx1, idx2, maxIdx = -1, -1, 0\n",
    "        for i in range(n):\n",
    "            if n_list[i] > n_list[maxIdx]:\n",
    "                maxIdx = i\n",
    "            elif n_list[i] < n_list[maxIdx]:\n",
    "                idx1, idx2 = i, maxIdx\n",
    "        if idx1 == -1:\n",
    "            return num\n",
    "        n_list[idx1], n_list[idx2] = n_list[idx2], n_list[idx1]\n",
    "        tmp = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tmp = 10 * tmp + n_list[i]\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        s = list(str(num))\n",
    "        n = len(s)\n",
    "        idx1 = idx2 = -1\n",
    "        maxIdx = n-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] > s[maxIdx]:\n",
    "                maxIdx = i\n",
    "            elif s[i] < s[maxIdx]:\n",
    "                idx1 = i\n",
    "                idx2 = maxIdx\n",
    "        if idx1 == -1:\n",
    "            return num\n",
    "        else:\n",
    "            s[idx1],s[idx2] = s[idx2], s[idx1]\n",
    "            return int(''.join(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        if num < 12: return num\n",
    "        sn = list(map(int, str(num)))\n",
    "        # print(sn)\n",
    "        book = SortedDict()\n",
    "        for i, x in enumerate(sn):\n",
    "            if x not in book: book[x] = deque()\n",
    "            book[x].append(i)\n",
    "        # print(book)\n",
    "        for i, x in enumerate(sn):\n",
    "            rx = book.keys()[-1]\n",
    "            if rx > x:\n",
    "                j = book[rx][-1]\n",
    "                res = sn.copy()\n",
    "                res[i], res[j] = res[j], res[i]\n",
    "                return int(''.join(map(str, res)))\n",
    "            else:\n",
    "                book[x].popleft()\n",
    "                if not book[x]: del book[x]\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        ans = num\n",
    "        s = list(str(num))\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i):\n",
    "                s[i], s[j] = s[j], s[i]\n",
    "                ans = max(ans, int(''.join(s)))\n",
    "                s[i], s[j] = s[j], s[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        ans = num\n",
    "        s = list(str(num))\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i):\n",
    "                s[i], s[j] = s[j], s[i]\n",
    "                ans = max(ans, int(''.join(s)))\n",
    "                s[i], s[j] = s[j], s[i]\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSwap(self, num: int) -> int:\n",
    "        num_str = str(num)\n",
    "        digits = [int(digit) for digit in num_str]\n",
    "        \n",
    "        # 记录每个数字最后出现的位置\n",
    "        last_occurrence = {digit: i for i, digit in enumerate(digits)}\n",
    "\n",
    "        # 从高位到低位遍历字符串\n",
    "        for i in range(len(digits)):\n",
    "            # 从9开始找到比当前位大的最大数字\n",
    "            for d in range(9, digits[i], -1):\n",
    "                if d in last_occurrence and last_occurrence[d] > i:\n",
    "                    # 找到最大数字后的最小数字\n",
    "                    j = last_occurrence[d]\n",
    "                    # 交换数字\n",
    "                    digits[i], digits[j] = digits[j], digits[i]\n",
    "                    # 将结果转换为整数并返回\n",
    "                    return int(\"\".join(map(str, digits)))\n",
    "\n",
    "        # 如果没有找到符合条件的交换，直接返回原数字\n",
    "        return num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
